package list.ReverseList;

import list.ListNode;

/**
 * @ClassName ReverseList2
 * @Description TODO
 * @Author lenovo
 * @Date 2023-02-15 9:44
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class ReverseList2 {
    /**
     * 题目
     * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
     * <p>
     * 示例1：
     * <p>
     * 输入：head = [1,2,3,4,5], left = 2, right = 4
     * 输出：[1,4,3,2,5]
     * 1
     * 2
     * 示例2：
     * <p>
     * 输入：head = [5], left = 1, right = 1
     * 输出：[5]
     * 1
     * 2
     * 思路
     * 查找到左右两个结点，单独对这两个结点之间的链表进行反转，将翻转后的结果拼接到原来的链表中。
     * 需要注意保留左节点的前一个结点，用于左节点的拼接
     */

    public ListNode reverseBetween(ListNode head, int left, int right) {

        if (left == right) {
            return head;
        }

        ListNode leftListNode = new ListNode(0);
        leftListNode.next = head;
        for (int i = 1; i < left; i++) {
            leftListNode = leftListNode.next;
        }

        ListNode rightListNode = new ListNode(0);
        rightListNode.next = head;
        for (int i = 0; i < right; i++) {
            rightListNode = rightListNode.next;
        }

        ListNode endListNode = rightListNode.next;

        ListNode q = leftListNode.next;
        leftListNode.next = endListNode;

        while (q != endListNode) {
            ListNode temp = q.next;
            q.next = leftListNode.next;
            leftListNode.next = q;
            q = temp;
        }
        return left == 1 ? leftListNode.next : head;
    }


    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(3);
        ListNode head4 = new ListNode(4);
        head1.next = head2;
        head2.next = head3;
        head3.next = head4;

        ReverseList2 reverseList = new ReverseList2();
        System.out.println(reverseList.reverseBetween(head1, 2, 3).toString());
    }

}